package 代码随想录.链表.两两交换链表中的节点;

import java.util.List;

/**lc24. 两两交换链表中的节点
 * lchttps://leetcode-cn.com/problems/swap-nodes-in-pairs/
 * @author ChenweiLin
 * @create 2021-12-02 20:59
 */
public class swapNodesInPairs {
    public static void main(String[] args) {

    }

    class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next;
    }
    ListNode swapPairs(ListNode head) {
        //伪头节点 方便return
        ListNode wei = new ListNode(-1,head);
        //只交换值
        while (head != null && head.next != null){//第二个条件排除奇数个剩余最后一个节点还要循环的情况
            int nextVal = head.next.val;//后一个节点的值
            int preVal = head.val;//前一个节点的值
            //step:节点值的互换
            head.val = nextVal;
            head.next.val = preVal;
            //每次向后移两位
            head = head.next.next;
        }


        return wei.next;

    }

        ListNode swapPairs2(ListNode head){
            //交换节点 不交换值
            //采用递归
            //step1:递归中止条件
            if(head == null || head.next == null){//到了末尾，奇数剩一个，偶数一个都不剩
                return head;
            }

            //step2:思考每一级应该返回给上一级上门
            //ans：返回给上一级已经处理好的链表

            //step3：本级递归应该做什么：在这一级递归中，应该完成什么任务？
            //ans：完成head和head.next以及剩余链表（next）的指针更换
            ListNode next = head.next;
            head.next = swapPairs(next.next);//swapPairs(next.next)返回值是从回溯看上一次递归返回的已处理好的链表，对于此处递归来看是剩余的已处理好的链表
                                             //next.next作为入参是因为题干所给的要求两两交换
            next.next = head;

            return next;//经历当前迭代后首节点变为next，return next也是return当前已处理好了的链表
        }

    }
}
